package mashibing.class23;

import java.util.Arrays;

/**
 * 给定一个正数数组arr，请把arr中所有的数分成两个集合
 * 如果arr长度为偶数，两个集合包含数的个数要一样多
 * 如果arr长度为奇数，两个集合包含数的个数必须只差一个
 * 请尽量让两个集合的累加和接近
 * 返回：
 * 最接近的情况下，较小集合的累加和
 */
public class Class23_2_SplitSumClosedSizeHalf {

    public static int splitSumClosedSizeHalf1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = Arrays.stream(arr).sum() / 2;
        if (arr.length % 2 == 0) {
            return process(arr, 0, arr.length / 2, sum);
        } else {
            return Math.max(process(arr, 0, arr.length / 2, sum), process(arr, 0, arr.length / 2 + 1, sum));
        }
    }

    private static int process(int[] arr, int i, int picks, int rest) {
        if (i == arr.length) {
            return picks == 0 ? 0 : -1;
        } else {
            int p1 = process(arr, i + 1, picks, rest);
            int p2 = -1;
            int next = -1;
            if (arr[i] <= rest) {
                next = process(arr, i + 1, picks - 1, rest - arr[i]);
            }
            if (next != -1) {
                p2 = arr[i] + next;
            }
            return Math.max(p1, p2);
        }
    }

    public static int splitSumClosedSizeHalf2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = Arrays.stream(arr).sum() / 2;

        int[][][] dp = new int[arr.length + 1][((arr.length + 1) / 2) + 1][sum + 1];
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= (arr.length + 1) / 2; j++) {
                for (int k = 0; k <= sum; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        for (int rest = 0; rest <= sum; rest++) {
            dp[arr.length][0][rest] = 0;
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            for (int pick = 0; pick <= (arr.length + 1) / 2; pick++) {
                for (int rest = 0; rest <= sum; rest++) {
                    int p1 = dp[i + 1][pick][rest];
                    int p2 = -1;
                    int next = -1;
                    if (arr[i] <= rest && pick > 0) {
                        next = dp[i + 1][pick - 1][rest - arr[i]];
                    }
                    if (next != -1) {
                        p2 = arr[i] + next;
                    }
                    dp[i][pick][rest] = Math.max(p1, p2);
                }
            }
        }
        if (arr.length % 2 == 0) {
            return process(arr, 0, arr.length / 2, sum);
        } else {
            return Math.max(process(arr, 0, arr.length / 2, sum), process(arr, 0, arr.length / 2 + 1, sum));
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 15, 31, 24, 20, 14, 16, 27, 28};
        System.out.println(splitSumClosedSizeHalf1(arr));      // 88
        System.out.println(splitSumClosedSizeHalf2(arr));      // 88
    }
}
